package DataStructure_ZL.单行非循环链表;

public class MySingleList {

    static class ListNode {
        public int val;//数值域
        public ListNode next;//存储下一个节点的地址

        public ListNode() {
        }

        public ListNode(int val) {
            this.val = val;
        }

        public boolean equals(ListNode obj) {
            if (obj == null) {
                return false;
            }
            return this.val == obj.val && this.next == obj.next;
        }
    }

    public ListNode head;//代表单链表的头结点的引用

    /**
     * 这里只是简单的进行，链表的构造。
     */
    //创建集合无元素
//        public void createList() {}

    //输出集合
    public void display() {
        if (this.head == null) {
            return;
        }
        ListNode cur = this.head;
        while (cur != null) {
            System.out.println(cur.val + "");
            cur = cur.next;
        }
        System.out.println();
    }

    //在集合开始的位置添加元素
    public void addFirst(int data) {
        //集合还没有任何元素
        if (this.head == null) {
            this.head = new ListNode(data);
            return;
        }
        //集合内有元素
        ListNode hr = new ListNode(data);
        hr.next = this.head;
        this.head = hr;
    }

    //尾插法 O(n)
    public void addLast(int data) {
        //集合还没有任何元素
        if (this.head == null) {
            this.head = new ListNode(data);
            return;
        }
        // 集合已经有了元素
        ListNode temp = this.head;//临时存储头节点
        while (true) {
            if (temp.next == null) {//当next等于null时表示是最后一个节点了
                temp.next = new ListNode(data);
                return;
            }
            temp = temp.next;
        }
    }

    //在指定的索引位置添加元素
    public void addIndex(int index, int data) {
        //集合还没有任何元素
        if (this.head == null) {
            this.head = new ListNode(data);
            return;
        }
        if (index < 0 || index >= size()) {
            throw new RuntimeException("索引越界");
        }
        // 集合已经有了元素
        // 当刚好是第一个节点时
        if (index == 0) {
            addFirst(data);
            return;
        }
        ListNode temp = this.head;//临时存储头节点
        for (int i = 1; i < this.size(); i++) {
            //没在第一个和最后一个位置的情况
            if (index == i) {
                //得到的都是索引的前一个节点
                ListNode newL = new ListNode(data);
                newL.next = temp.next;
                temp.next = newL;
                return;
            }
            temp = temp.next;
        }
    }

    //查找是否包含关键字key是否在单链表当中  314
    public boolean contains(int key) {
        if (this.head == null) {
            System.out.println("当前集合还没有任何元素");
            return false;
        }
        ListNode temp = this.head;//临时存储头节点
        do {
            if (temp.val == key) {
                return true;
            }
            temp = temp.next;
        } while (temp != null);
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (this.head == null) {
            System.out.println("当前集合还没有任何元素");
            return;
        }
        //刚好是第一个元素
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode temp = this.head;//临时存储头节点
        while (temp.next != null) {
            if (temp.next.val == key) {
                temp.next = temp.next.next;
                return;
            }
            temp = temp.next;
        }
        System.out.println("集合中没有该元素");
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if (this.head == null) {
            System.out.println("当前集合还没有任何元素");
            return;
        }
        //刚好是第一个元素
        while (true) {
            if (this.head.val == key) {
                this.head = this.head.next;
            }
            //如果索引当中所有的值都为要删除的值那么head最终会为null
            if (this.head == null) {
                return;
            }
            if (this.head.val != key) {
                break;
            }
        }
        ListNode temp = this.head;//临时存储头节点
        while (temp.next != null) {
            if (temp.next.val == key) {
                while (true) {
                    temp.next = temp.next.next;
                    if (temp.next == null) {
                        return;
                    }
                    if (temp.next.val != key) {
                        break;
                    }
                }
            }
            temp = temp.next;
        }
    }

    //得到单链表的长度
    public int size() {

        //集合为空的时候
        if (this.head == null) {
            return 0;
        }
        //集合不为空说明至少有一个以上的元素
        int index = 1;//存储链表的长度
        ListNode temp = this.head;//临时存储头节点
        while (temp.next != null) {
            index++;
            temp = temp.next;
        }
        return index;
    }

    //清除所有元素
    public void clear() {
        this.head = null;
    }

    //力扣题目
    /*
    给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足
    Node.val == val 的节点，并返回 新的头节点 。
     */
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode hur = head.next;
        while (hur != null) {
            if (hur.val == val) {
                cur.next = hur.next;
                hur = hur.next;
            } else {
                cur = hur;
                hur = hur.next;
            }
        }
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }

    /*
    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        //排除只有一个元素的情况
        if (head.next == null) {
            return head;
        }
        ListNode sllow = head.next;
        ListNode fast = head.next.next;
        head.next = null;
        while (fast != null) {
            sllow.next = head;
            head = sllow;
            sllow = fast;
            fast = fast.next;
        }
        sllow.next = head;
        head = sllow;
        return head;
    }

    /*
    给定一个头结点为 head 的非空单链表，返回链表的中间结点。
    如果有两个中间结点，则返回第二个中间结点。
     */
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /*
    输入一个链表，输出该链表中倒数第k个结点。
     */
    public ListNode FindKthToTail(ListNode head, int k) {
        if (k < 0) {
            return null;
        }
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (k - 1 > 0) {
            fast = fast.next;
            if (fast.next == null) {
                return null;
            }
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    /*
    将两个升序链表合并为一个新的 升序 链表并返回。
    新链表是通过拼接给定的两个链表的所有节点组成的。
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode result = new ListNode();//接收新链表的头结点
        ListNode temp = result;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                temp.next = list1;
                list1 = list1.next;
                temp = temp.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
                temp = temp.next;
            }
        }
        if (list1 == null) {
            temp.next = list2;
        }
        if (list2 == null) {
            temp.next = list1;
        }
        result = result.next;//把第一个创建的无关节点去除
        return result;
    }

    /*
    对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法
    ，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，
    代表其是否为回文结构。保证链表长度小于等于900。
     */
    public boolean chkPalindrome(ListNode A) {
        //得到中间节点
        ListNode slow = A;
        ListNode fast = A;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //将中间节点后面的节点反转
        ListNode s = slow.next;
        ListNode f = slow.next;
        while (f.next != null) {
            f = f.next;
            s.next = slow;
            slow = s;
            s = f;
        }
        s.next = slow;
        slow = s;
        //判断是不是回文数
        while (true) {
            if (A.val == slow.val) {
                A = A.next;
                slow = slow.next;
                if (A.next == slow.next || A.next == slow) {
                    return true;
                }
            }
            if (A.val != slow.val) {
                return false;
            }
        }
    }

    /*
    现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的
    结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
     */
    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) return null;
        ListNode cur = pHead;
        ListNode bs = null;//前半部分开始
        ListNode be = null;//前半部分结束
        ListNode as = null;//后半部分开始
        ListNode ae = null;//后半部分结束
        while (cur != null) {
            if (cur.val < x) {
                //小于x部分
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = cur;
                }
            } else {
                //大于等于x部分
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = cur;
                }
            }
            cur = cur.next;
        }
        //如果小于部分为空
        if (bs == null) return as;
        //如果大于等于部分为空
        if (as != null) ae.next = null;
        be.next = as;//将两部分连接起来
        return bs;
    }

    /*
    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表
    相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null)return null;
        if (headB==null)return null;

        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int countA = 0;
        int countB = 0;
        while (cur1 != null) {
            countA++;
            cur1 = cur1.next;
        }
        cur1 = headA;//重新指向头节点
        while (cur2 != null) {
            countB++;
            cur2 = cur2.next;
        }
        cur2 = headB;
        int result = countA - countB;
        if (result > 0) {
            //headA比headB长
            while (result > 0) {
                cur1 = cur1.next;
                result--;
            }
        } else {
            while (result < 0) {
                cur2 = cur2.next;
                result++;
            }
        }
        while(cur1!=null){
            if (cur1==cur2){
                return cur1;
            }
            cur1=cur1.next;
            cur2=cur2.next;
        }
        return null;
    }

    /*
    给你一个链表的头节点 head ，判断链表中是否有环。
     */
    public boolean hasCycle(ListNode head) {
        if (head==null) return false;
        //用快慢指针解决
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if (slow==fast){
                return true;
            }
        }
        return false;
    }
}







